'''
找到链表的倒数第k个节点
'''

'''
思路：
    设链表长度为l，先让头指针走k步，此时距链表尾部还有l-k步，则让指针和另一个头指针同时走，
    当前指针走到尾部时，另一头指针刚好走到倒数第k个节点的前一个
'''
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        p,q = head,head
        for i in range(cnt):
            p = p.next
        while p:
            q = q.next
            p = p.next
        return q
    
    '''
    先遍历一次链表记录长度，再次遍历到倒数第k个节点
    '''

    def trainingPlan2(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        p,q = head,head
        len = 0
        while p:
            p = p.next
            len += 1
        diff = len - cnt
        for i in range(diff):
            q = q.next
        return q